package com.c2b.algorithm.leetcode.base;

import java.util.Deque;
import java.util.LinkedList;

/**
 * <a href='https://leetcode.cn/problems/add-two-numbers-ii/'> 两数相加 II(Add Two Numbers II)</a>
 * <p>给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。</p>
 * <p>你可以假设除了数字 0 之外，这两个数字都不会以零开头。</p>
 *
 * <p>
 * <pre>
 * 示例1：
 *      输入：l1 = [7,2,4,3], l2 = [5,6,4]
 *      输出：[7,8,0,7]
 *
 * 示例2：
 *      输入：l1 = [2,4,3], l2 = [5,6,4]
 *      输出：[8,0,7]
 *
 * 示例3：
 *      输入：l1 = [0], l2 = [0]
 *      输出：[0]
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>链表的长度范围为 [1, 100]</li>
 *     <li>0 <= node.val <= 9</li>
 *     <li>输入数据保证链表代表的数字无前导 0</li>
 * </ul>
 * </p>
 * <b>进阶：如果输入链表不能翻转该如何解决？</b>
 * @author c2b
 * @since 2023/5/9 16:33
 */
public class LC0445AddTwoNumbers_II_M {

    static class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            Deque<Integer> deque1 = new LinkedList<>();
            while (l1 != null) {
                deque1.addFirst(l1.val);
                l1 = l1.next;
            }
            Deque<Integer> deque2 = new LinkedList<>();
            while (l2 != null) {
                deque2.addFirst(l2.val);
                l2 = l2.next;
            }
            // 进位
            int carry = 0;
            ListNode ans = null;
            while (!deque1.isEmpty() || !deque2.isEmpty() || carry == 1) {
                int val = (deque1.isEmpty() ? 0 : deque1.removeFirst()) + (deque2.isEmpty() ? 0 : deque2.removeFirst()) + carry;
                carry = val / 10;
                ListNode newNode = new ListNode(val % 10);
                newNode.next = ans;
                ans = newNode;
            }
            return ans;
        }
    }

    public static void main(String[] args) {
        //ListNode l1 = new ListNode(9);
        //l1.next = new ListNode(9);
        ListNode l1 = new ListNode(7);
        l1.next = new ListNode(2);
        l1.next.next = new ListNode(4);
        l1.next.next.next = new ListNode(3);
        //ListNode l2 = new ListNode(9);
        ListNode l2 = new ListNode(5);
        l2.next = new ListNode(6);
        l2.next.next = new ListNode(4);
        Solution solution = new Solution();
        Printer.printListNode(solution.addTwoNumbers(l1, l2));
    }
}
